package org.usmile.algorithms.leetcode.middle;

/**
 * 861. 翻转矩阵后的得分
 *
 * 给你一个大小为 m x n 的二元矩阵 grid ，矩阵中每个元素的值为 0 或 1 。
 * 一次 移动 是指选择任一行或列，并转换该行或列中的每一个值：将所有 0 都更改为 1，将所有 1 都更改为 0。
 * 在做出任意次数的移动后，将该矩阵的每一行都按照二进制数来解释，矩阵的 得分 就是这些数字的总和。
 * 在执行任意次 移动 后（含 0 次），返回可能的最高分数。
 *
 * 示例 1：
 * 输入：grid = [[0,0,1,1],[1,0,1,0],[1,1,0,0]]
 * 输出：39
 * 解释：0b1111 + 0b1001 + 0b1111 = 15 + 9 + 15 = 39
 *
 * 示例 2：
 * 输入：grid = [[0]]
 * 输出：1
 *
 * 提示：
 * m == grid.length
 * n == grid[i].length
 * 1 <= m, n <= 20
 * grid[i][j] 为 0 或
 */
public class _0861 {
}

class _0861_Solution {
    public int matrixScore(int[][] grid) {
        int rows = grid.length;
        int cols = grid[0].length;
        // 使得每一行都从 1 开头
        for (int row = 0; row < rows; row++) {
            if (grid[row][0] == 0) {
                // 行翻转
                for (int col = 0; col < cols; col++) {
                    grid[row][col] ^= 1;
                }
            }
        }

        int max = 0;
        // 1 的数量越多，得到的数值越大
        for (int col = 0; col < cols; col++) {
            int cnt = 0;
            // 统计第 col 列有多少个 1。
            for (int row = 0; row < rows; row++) {
                cnt += grid[row][col];
            }

            int maxOneCnt = Math.max(cnt, rows - cnt);
            max += maxOneCnt * (1 << (cols - col - 1));
        }

        return max;
    }
}